// 版权归Go作者所有。保留所有权利。
// 此源代码的使用受BSD样式
// 许可证的约束，该许可证可以在许可证文件中找到。

// backtrack是一种正则表达式搜索，带有子匹配
// 跟踪小正则表达式和文本。它分配
// 一个带有（输入长度）*（程序长度）位的位向量，
// 以确保它不会多次探索相同的（字符位置、指令）
// 状态。这限制了搜索在
// 测试长度中的时间线性运行。
// 
// backtrack是在无法使用onepass时，在小型
// regexp上快速替换NFA代码。

package regexp

import (
	"regexp/syntax"
	"sync"
)

// 作业是回溯程序作业堆栈中的一个条目。它保存
// 指令pc和输入中的位置。
type job struct {
	pc  uint32
	arg bool
	pos int
}

const (
	visitedBits        = 32
	maxBacktrackProg   = 500        // len（prog.Inst）<=max 
	maxBacktrackVector = 256 * 1024 // 位向量大小<=max（bits）
)

// bitState保留回溯程序的状态。
type bitState struct {
	end      int
	cap      []int
	matchcap []int
	jobs     []job
	visited  []uint32

	inputs inputs
}

var bitStatePool sync.Pool

func newBitState() *bitState {
	b, ok := bitStatePool.Get().(*bitState)
	if !ok {
		b = new(bitState)
	}
	return b
}

func freeBitState(b *bitState) {
	b.inputs.clear()
	bitStatePool.Put(b)
}

// maxBitStateLen返回要使用
// 使用prog的回溯程序搜索的字符串的最大长度。
func maxBitStateLen(prog *syntax.Prog) int {
	if !shouldBacktrack(prog) {
		return 0
	}
	return maxBacktrackVector / len(prog.Inst)
}

// shouldldbacktrack报告程序是否太长
// backtrack无法运行。
func shouldBacktrack(prog *syntax.Prog) bool {
	return len(prog.Inst) <= maxBacktrackProg
}

// 重置后向跟踪器的状态。
// end是输入中的结束位置。
// ncap是捕获的数量。
func (b *bitState) reset(prog *syntax.Prog, end int, ncap int) {
	b.end = end

	if cap(b.jobs) == 0 {
		b.jobs = make([]job, 0, 256)
	} else {
		b.jobs = b.jobs[:0]
	}

	visitedSize := (len(prog.Inst)*(end+1) + visitedBits - 1) / visitedBits
	if cap(b.visited) < visitedSize {
		b.visited = make([]uint32, visitedSize, maxBacktrackVector/visitedBits)
	} else {
		b.visited = b.visited[:visitedSize]
		for i := range b.visited {
			b.visited[i] = 0
		}
	}

	if cap(b.cap) < ncap {
		b.cap = make([]int, ncap)
	} else {
		b.cap = b.cap[:ncap]
	}
	for i := range b.cap {
		b.cap[i] = -1
	}

	if cap(b.matchcap) < ncap {
		b.matchcap = make([]int, ncap)
	} else {
		b.matchcap = b.matchcap[:ncap]
	}
	for i := range b.matchcap {
		b.matchcap[i] = -1
	}
}

// shouldVisit报告（pc、pos）组合是否尚未访问
// 。
func (b *bitState) shouldVisit(pc uint32, pos int) bool {
	n := uint(int(pc)*(b.end+1) + pos)
	if b.visited[n/visitedBits]&(1<<(n&(visitedBits-1))) != 0 {
		return false
	}
	b.visited[n/visitedBits] |= 1 << (n & (visitedBits - 1))
	return true
}

// 如果作业堆栈应该是
// 则将（pc、pos、arg）推送到作业堆栈上。
func (b *bitState) push(re *Regexp, pc uint32, pos int, arg bool) {
	// 仅在arg为false时检查shouldVisit。
	// 如果arg为真，我们将继续之前的访问。
	if re.prog.Inst[pc].Op != syntax.InstFail && (arg || b.shouldVisit(pc, pos)) {
		b.jobs = append(b.jobs, job{pc: pc, arg: arg, pos: pos})
	}
}

// tryBacktrack从位置开始运行回溯搜索。
func (re *Regexp) tryBacktrack(b *bitState, i input, pc uint32, pos int) bool {
	longest := re.longest

	b.push(re, pc, pos, false)
	for len(b.jobs) > 0 {
		l := len(b.jobs) - 1
		// Pop job off the stack。
		pc := b.jobs[l].pc
		pos := b.jobs[l].pos
		arg := b.jobs[l].arg
		b.jobs = b.jobs[:l]

		// 优化：与push and pop不同，
		// 将要推动并继续的代码
		// 循环只更新ip、p和arg 
		// 并跳到CheckAndLoop。我们必须进行ShouldVisit检查，这是Push-
		// 应该做的，但是我们避免了堆栈
		// 操作。
		goto Skip
	CheckAndLoop:
		if !b.shouldVisit(pc, pos) {
			continue
		}
	Skip:

		inst := re.prog.Inst[pc]

		switch inst.Op {
		default:
			panic("bad inst")
		case syntax.InstFail:
			panic("unexpected InstFail")
		case syntax.InstAlt:
			// 不能只是
			// b.push（inst.Out，pos，false）
			// b.push（inst.Arg，pos，false）
			// 如果在inst.Out的处理过程中，我们通过另一条路径遇到了
			// inst.Arg，那么我们想处理它。
			// 将其推到此处将抑制该行为。相反，用arg==true重新推送
			// inst，以提醒以后将inst.arg推出
			// 。
			if arg {
				// 安装完毕；试试inst.Arg。
				arg = false
				pc = inst.Arg
				goto CheckAndLoop
			} else {
				b.push(re, pc, pos, true)
				pc = inst.Out
				goto CheckAndLoop
			}

		case syntax.InstAltMatch:
			// 一个操作码消耗符文；另一个是匹配的。
			switch re.prog.Inst[inst.Out].Op {
			case syntax.InstRune, syntax.InstRune1, syntax.InstRuneAny, syntax.InstRuneAnyNotNL:
				// inst.Arg是匹配项。
				b.push(re, inst.Arg, pos, false)
				pc = inst.Arg
				pos = b.end
				goto CheckAndLoop
			}
			// inst.Out是匹配-非贪婪
			b.push(re, inst.Out, b.end, false)
			pc = inst.Out
			goto CheckAndLoop

		case syntax.InstRune:
			r, width := i.step(pos)
			if !inst.MatchRune(r) {
				continue
			}
			pos += width
			pc = inst.Out
			goto CheckAndLoop

		case syntax.InstRune1:
			r, width := i.step(pos)
			if r != inst.Rune[0] {
				continue
			}
			pos += width
			pc = inst.Out
			goto CheckAndLoop

		case syntax.InstRuneAnyNotNL:
			r, width := i.step(pos)
			if r == '\n' || r == endOfText {
				continue
			}
			pos += width
			pc = inst.Out
			goto CheckAndLoop

		case syntax.InstRuneAny:
			r, width := i.step(pos)
			if r == endOfText {
				continue
			}
			pos += width
			pc = inst.Out
			goto CheckAndLoop

		case syntax.InstCapture:
			if arg {
				// /完成inst.Out；恢复旧的价值。
				b.cap[inst.Arg] = pos
				continue
			} else {
				if inst.Arg < uint32(len(b.cap)) {
					// 捕获要注册的pos，但保存旧值。
					b.push(re, pc, b.cap[inst.Arg], true) // 完成后请回来。
					b.cap[inst.Arg] = pos
				}
				pc = inst.Out
				goto CheckAndLoop
			}

		case syntax.InstEmptyWidth:
			flag := i.context(pos)
			if !flag.match(syntax.EmptyOp(inst.Arg)) {
				continue
			}
			pc = inst.Out
			goto CheckAndLoop

		case syntax.InstNop:
			pc = inst.Out
			goto CheckAndLoop

		case syntax.InstMatch:
			// 我们找到了匹配的。如果打电话的人不在乎
			// 比赛在哪里，那就没必要再继续了。
			if len(b.cap) == 0 {
				return true
			}

			// 创下迄今为止最好的比赛记录。
			// 只需要检查端点，因为整个
			// 调用只考虑一个起始位置。
			if len(b.cap) > 1 {
				b.cap[1] = pos
			}
			if old := b.matchcap[1]; old == -1 || (longest && pos > 0 && pos > old) {
				copy(b.matchcap, b.cap)
			}

			// 如果参加第一场比赛，我们就完了。
			if !longest {
				return true
			}

			// 如果我们使用了整个文本，就不可能再匹配了。
			if pos == b.end {
				return true
			}

			// 否则，继续比赛，希望比赛时间更长。
			continue
		}
	}

	return longest && len(b.matchcap) > 1 && b.matchcap[1] >= 0
}

// backtrack从位置开始对输入进行prog的回溯搜索。
func (re *Regexp) backtrack(ib []byte, is string, pos int, ncap int, dstCap []int) []int {
	startCond := re.cond
	if startCond == ^syntax.EmptyOp(0) { // 不可能的
		return nil
	}
	if startCond&syntax.EmptyBeginText != 0 && pos != 0 {
		// 锚定匹配，超过文本开头。
		return nil
	}

	b := newBitState()
	i, end := b.inputs.init(nil, ib, is)
	b.reset(re.prog, end, ncap)

	// 定位搜索必须从输入的开始处开始
	if startCond&syntax.EmptyBeginText != 0 {
		if len(b.cap) > 0 {
			b.cap[0] = pos
		}
		if !re.tryBacktrack(b, i, uint32(re.prog.Start), pos) {
			freeBitState(b)
			return nil
		}
	} else {

		// 未定位搜索，从每个可能的文本位置开始。
		// 注意，我们必须尝试
		// 文本末尾的空字符串，因此循环条件是pos<=end，而不是pos<end。
		// 这看起来像是文本大小的二次函数，
		// 但是我们没有在调用TrySearch之间清除访问量，所以没有重复工作，结果仍然是线性的。
		width := -1
		for ; pos <= end && width != 0; pos += width {
			if len(re.prefix) > 0 {
				// 匹配需要文字前缀；快速搜索。
				advance := i.index(re, pos)
				if advance < 0 {
					freeBitState(b)
					return nil
				}
				pos += advance
			}

			if len(b.cap) > 0 {
				b.cap[0] = pos
			}
			if re.tryBacktrack(b, i, uint32(re.prog.Start), pos) {
				// 匹配必须是最左边的；完成。
				goto Match
			}
			_, width = i.step(pos)
		}
		freeBitState(b)
		return nil
	}

Match:
	dstCap = append(dstCap, b.matchcap...)
	freeBitState(b)
	return dstCap
}
